package algorithm;

import java.util.*;

public class LinkedListMid {

    public static class Node implements Comparable<Node>{//实例内部类不能声明静态成员
        public int value;
        public Node next;
        public Node rand;

        public Node(int value){
            this.value=value;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Node node = (Node) o;
            return value == node.value;
        }

        @Override
        public int hashCode() {
            return Objects.hash(value);
        }

        @Override
        public String toString() {
            return "Node{" +
                    "value=" + value +
                    '}';
        }

        @Override
        public int compareTo(Node o) {
            return this.value==o.value?0:this.value<o.value?-1:1;
        }
    }

//快慢指针找中间节点==============================================================================
    public static Node midOrUpMidNode(Node head){
        if(head==null || head.next==null || head.next.next==null)
            return head;
        Node slow = head.next;//第二个节点
        Node fast = head.next.next;//第三个节点
        while(fast.next!=null && fast.next.next!=null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    public static Node midOrDownMidNode(Node head){
        if(head==null || head.next==null )
            return head;
        Node slow = head.next;//第二个节点
        Node fast = head.next;//第三个节点
        while(fast.next!=null && fast.next.next!=null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    public static Node midOrUpMidPreNode(Node head){
        if(head==null || head.next==null || head.next.next==null)
            return null;
        Node slow = head;//第一个节点
        Node fast = head.next.next;//第三个节点
        while(fast.next!=null && fast.next.next!=null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    public static Node midOrDownMidPreNode(Node head){
        if(head==null || head.next==null )
            return null;
        Node slow = head;//第二个节点
        Node fast = head.next;//第三个节点
        while(fast.next!=null && fast.next.next!=null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    public static Node right4(Node head) {
        if (head == null || head.next == null) {
            return null;
        }
        Node cur = head;
        ArrayList<Node> arr = new ArrayList<>();
        while (cur != null) {
            arr.add(cur);
            cur = cur.next;
        }
        return arr.get((arr.size() - 2) / 2);
    }

 //回文===================================================================================
    public static boolean isPalinDrome(Node head){

        if(head==null)
            return true;
        Node slow = head;
        Node fast = head;
        while(fast.next!=null && fast.next.next!=null){
            slow = slow.next;
            fast = fast.next.next;
        }
        Node right = slow.next;
        Stack<Node> stack = new Stack<>();
        while(right!=null){
            stack.push(right);
            right = right.next;
        }

        Node left = head;
        while(!stack.isEmpty()){
            if(!stack.pop().equals(left))
                return false;
            left = left.next;
        }
        return true;
    }

    public static boolean isPalinDrome2(Node head){

        if(head==null)
            return true;
        Node slow = head;
        Node fast = head;
        while(fast.next!=null && fast.next.next!=null){
            slow = slow.next;
            fast = fast.next.next;
        }
        Node right = slow.next;
        slow.next = null;
        Node rightNext = right.next;
        right.next = slow;
        Node pre = right;
        while(rightNext!=null){
            right = rightNext;
            rightNext = right.next;
            right.next = pre;
            pre = right;
        }

        Node left = head;
        boolean a = true;
        Node rightPre = null;
        rightNext = null;
        while(right.next!=null){
            if(a==true){
                a = left.equals(right)?true:false;
            }
            left = left.next;
            rightPre = right.next;
            right.next = rightNext;
            rightNext = right;
            right = rightPre;
        }
        right.next = rightNext;
        return a;
    }


//链表快排=================================================================================
    public static void swap(Node[] nodes, int i, int j){
        Node temp = nodes[i];
        nodes[i] = nodes[j];
        nodes[j] = temp;
    }
    public static void arrPartition(Node[] arr , int pivot){
        if(arr==null)
            return;
        int index = 0;
        int less = -1;
        int more = arr.length;
        while(index < more){
            if(arr[index].value < pivot){
                swap(arr, ++less, index++);
            }else
                if(arr[index].value == pivot){
                    index++;
                }else
                    swap(arr, index, --more);
        }
    }

    public static  Node listPartition1(Node head, int pivot) {
        if(head == null)
            return null;
        ArrayList<Node> list = new ArrayList<>();
        while(head != null){
            list.add(head);
            head = head.next;
        }

        Node[] arr = (Node[]) list.toArray(new Node[list.size()]);
        arrPartition(arr, pivot);
        Node newhead = arr[0];
        Node temp = newhead;
        for (int i = 1; i < arr.length; i++) {
            temp.next = arr[i];
            temp = temp.next;
        }
        temp.next = null;
        return newhead;
    }

    public static  Node listPartition2(Node head, int pivot) {
        if(head == null)
            return null;
        Node sH = null;
        Node sT = null;
        Node eH = null;
        Node eT = null;
        Node mH = null;
        Node mT = null;

        Node index = head;
        while(index != null){
            if(index.value < pivot){
                if(sH == null){
                    sH = index;
                    sT = index;
                }else{
                    sT.next = index;
                    sT = index;
                }
            }else
                if(index.value == pivot){
                   if(eH == null){
                       eH = index;
                       eT = index;
                   }else{
                       eT.next = index;
                       eT = index;
                   }
                }else {
                    if(mH == null){
                        mH = index;
                        mT = index;
                    }else{
                        mT.next = index;
                        mT = index;
                    }
                }
            index = index.next;
        }
        Node newhead = new Node(Integer.MIN_VALUE);
        index = newhead;
        if(sH != null){
            index.next = sH;
            index = sT;
        }
        if(eH != null){
            index.next = eH;
            index = eT;
        }
        if(mH != null){
            index.next = mH;
            index = mT;
        }
        index.next = null;
        return newhead.next;
    }

    public static void printLinkedList(Node node) {
        System.out.print("Linked List: ");
        while (node != null) {
            System.out.print(node.value + " ");
            node = node.next;
        }
        System.out.println();
    }


//带随机指向链表的复制==========================================================================

    public static Node copyListWithRand1(Node head) {
        if(head == null)
            return null;
        HashMap<Node,Node> map =new HashMap<>();
        Node index = head;
        while (index != null){
            map.put(index, new Node(index.value));
            index = index.next;
        }
        index = head;
        while(index != null){
            map.get(index).next = map.get(index.next);
            map.get(index).rand = map.get(index.rand);
            index = index.next;
        }
        return map.get(head);
    }

    public static Node copyListWithRand2(Node head) {
        if(head == null)
            return null;
        Node index = head;
        while(index != null){
            Node copy = new Node(index.value);
            copy.next = index.next;
            index.next = copy;
            index = index.next.next;
        }
        index = head;
        while(index != null){
            if(index.rand != null)
                index.next.rand = index.rand.next;
           index = index.next.next;
        }
        Node copyList = head.next;
        index = head;
        Node copyIndex = copyList;
        Node temp = null;
        while(copyIndex.next != null){
            temp = copyIndex.next;
            copyIndex.next = copyIndex.next.next;
            index.next = temp;
            index = index.next;
            copyIndex = copyIndex.next;
        }
        index.next = null;
        return copyList;
    }

    public static void printRandLinkedList(Node head) {
        Node cur = head;
        System.out.print("order: ");
        while (cur != null) {
            System.out.print(cur.value + " ");
            cur = cur.next;
        }
        System.out.println();
        cur = head;
        System.out.print("rand:  ");
        while (cur != null) {
            System.out.print(cur.rand == null ? "- " : cur.rand.value + " ");
            cur = cur.next;
        }
        System.out.println();
    }

//可能有环可能无环的大链表相交，返回相交的第一个节点============================================

    public static Node getIntersectNode(Node head1, Node head2) {
        if (head1 == null || head2 == null) {
            return null;
        }
        Node loop1 = getLoopNode(head1);
        Node loop2 = getLoopNode(head2);
        if (loop1 == null && loop2 == null) {
            return noLoop(head1, head2);
        }
        if (loop1 != null && loop2 != null) {
            return bothLoop(head1, loop1, head2, loop2);
        }
        return null;
    }

    //得到第一个入环节点
    public static Node getLoopNode(Node head) {
        if(head == null || head.next ==null || head.next.next ==null)
            return null;
        Node slow = head.next;
        Node fast = head.next.next;
        while(slow != fast){
            if(fast.next == null || fast.next.next == null)
                return null;
            slow = slow.next;
            fast = fast.next.next;
        }
        fast = head;
        while(fast != slow){
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }

    // 如果两个链表都无环，返回第一个相交节点，如果不想交，返回null
    public static Node noLoop(Node head1, Node head2) {
        if(head1 == null || head2 == null)
            return null;
        int n=0;
        Node index = head1;
        while(index != null){
            n++;
            index = index.next;
        }
        index = head2;
        while(index != null){
            n--;
            index = index.next;
        }
        if(n > 0){
            index = head1;
            for (int i = 0; i < n; i++)
                index = index.next;
            Node index2 = head2;
            while(index != index2){
                index = index.next;
                index2 = index2.next;
            }
            return index;
        }else{
            index = head2;
            n = Math.abs(n);
            for (int i = 0; i < n; i++)
                index = index.next;
            Node index2 = head1;
            while(index != index2){
                index = index.next;
                index2 = index2.next;
            }
            return index;
        }

    }

    // 两个有环链表，返回第一个相交节点，如果不想交返回null
    public static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2) {
        if(head1 == null || loop1 == null || head2 == null || loop2 == null)
            return null;
        if(loop1 == loop2){
            HashSet<Node> nodeSet = new HashSet<>();
            Node index1 = head1;
            Node index2 = head2;
            do {
                nodeSet.add(index1);
                index1 = index1.next;
            }while(index1 != loop1);
            do {
                if(nodeSet.contains(index2))
                    break;
                index2 = index2.next;
            }while (index2 != loop2);
            return index2;
        }else {
            boolean a = false;
            Node index = head1;
            while(index != loop1)
                index = index.next;
            while (index.next != loop1){
                if(index.next == loop2){
                    a = true;
                    break;
                }
                index = index.next;
            }
            if(a){
                return loop2;
            }else
                return null;
        }
    }

    public static void main(String[] args) {
//        new LinkedListMid.Node();

//        Node test = null;
//        test = new Node(0);
//        test.next = new Node(1);
//        test.next.next = new Node(2);
//        test.next.next.next = new Node(3);
//        test.next.next.next.next = new Node(4);
//        test.next.next.next.next.next = new Node(3);
//        test.next.next.next.next.next.next = new Node(2);
//        test.next.next.next.next.next.next.next = new Node(1);
//        test.next.next.next.next.next.next.next.next = new Node(0);
//
//        Node ans1 = null;
//        Node ans2 = null;
//
//        ans1 = midOrDownMidPreNode(test);
//        ans2 = right4(test);
//        System.out.println(ans1 != null ? ans1.value : "无");
//        System.out.println(ans2 != null ? ans2.value : "无");
//
//        boolean palinDrome = isPalinDrome2(test);
//        System.out.println(palinDrome);
//        while(test!=null){
//            System.out.println(test);
//            test = test.next;
//        }

//        Node head1 = new Node(7);
//        head1.next = new Node(9);
//        head1.next.next = new Node(1);
//        head1.next.next.next = new Node(8);
//        head1.next.next.next.next = new Node(5);
//        head1.next.next.next.next.next = new Node(2);
//        head1.next.next.next.next.next.next = new Node(5);
//        printLinkedList(head1);
//        head1 = listPartition2(head1, 5);
////        head1 = listPartition2(head1, 5);
//        printLinkedList(head1);

//        Node head = null;
//        Node res1 = null;
//        Node res2 = null;
//        printRandLinkedList(head);
//        res1 = copyListWithRand1(head);
//        printRandLinkedList(res1);
//        res2 = copyListWithRand2(head);
//        printRandLinkedList(res2);
//        printRandLinkedList(head);
//        System.out.println("=========================");
//
//        head = new Node(1);
//        head.next = new Node(2);
//        head.next.next = new Node(3);
//        head.next.next.next = new Node(4);
//        head.next.next.next.next = new Node(5);
//        head.next.next.next.next.next = new Node(6);
//
//        head.rand = head.next.next.next.next.next; // 1 -> 6
//        head.next.rand = head.next.next.next.next.next; // 2 -> 6
//        head.next.next.rand = head.next.next.next.next; // 3 -> 5
//        head.next.next.next.rand = head.next.next; // 4 -> 3
//        head.next.next.next.next.rand = null; // 5 -> null
//        head.next.next.next.next.next.rand = head.next.next.next; // 6 -> 4
//
//        printRandLinkedList(head);
//        res1 = copyListWithRand1(head);
//        printRandLinkedList(res1);
//        res2 = copyListWithRand2(head);
//        printRandLinkedList(res2);
//        printRandLinkedList(head);
//        System.out.println("=========================");


        // 1->2->3->4->5->6->7->null
        Node head1 = new Node(1);
        head1.next = new Node(2);
        head1.next.next = new Node(3);
        head1.next.next.next = new Node(4);
        head1.next.next.next.next = new Node(5);
        head1.next.next.next.next.next = new Node(6);
        head1.next.next.next.next.next.next = new Node(7);

        // 0->9->8->6->7->null
        Node head2 = new Node(0);
        head2.next = new Node(9);
        head2.next.next = new Node(8);
        head2.next.next.next = head1.next.next.next.next.next; // 8->6
        System.out.println(getIntersectNode(head1, head2).value);//6

        // 1->2->3->4->5->6->7->4...
        head1 = new Node(1);
        head1.next = new Node(2);
        head1.next.next = new Node(3);
        head1.next.next.next = new Node(4);
        head1.next.next.next.next = new Node(5);
        head1.next.next.next.next.next = new Node(6);
        head1.next.next.next.next.next.next = new Node(7);
        head1.next.next.next.next.next.next = head1.next.next.next; // 7->4

        // 0->9->8->2...
        head2 = new Node(0);
        head2.next = new Node(9);
        head2.next.next = new Node(8);
        head2.next.next.next = head1.next; // 8->2
        System.out.println(getIntersectNode(head1, head2).value);//2

        // 0->9->8->6->4->5->6..
        head2 = new Node(0);
        head2.next = new Node(9);
        head2.next.next = new Node(8);
        head2.next.next.next = head1.next.next.next.next.next; // 8->6
        System.out.println(getIntersectNode(head1, head2).value);//4
    }
}
